package com.zklh.leetcode.interviewTop150;

import com.zklh.leetcode.other.problem1.ListNode;

/**
 * 反转链表II
 */
public class Solution92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode headPrev = new ListNode(-1),reversedPrev, reversedHead, reversedLast = head, reversedPost = null;
        reversedPrev = headPrev;
        reversedPrev.next = head;
        for (int i = 1; i < left; i++) {
            reversedPrev = reversedPrev.next;
        }
        reversedHead = reversedPrev.next;

        for (int i = 1; i < right; i++) {
            reversedLast = reversedLast.next;
        }
        reversedPost = reversedLast.next;

        reversedPrev.next = null;
        reversedLast.next = null;
        reverse(reversedHead);
        reversedPrev.next = reversedLast;
        reversedHead.next = reversedPost;
        return headPrev.next;
    }

    private ListNode reverse(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode nextTail = head.next;
        ListNode newHead = reverse(head.next);
        nextTail.next = head;
        head.next = null;
        return newHead;
    }


    public static void main(String[] args) {
        Solution92 solution = new Solution92();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode reverse = solution.reverseBetween(head, 2, 4);
        System.out.println(reverse);
    }
}
